/*
 * @lc app=leetcode.cn id=126 lang=golang
 *
 * [126] 单词接龙 II
 */

// @lc code=start
func findLadders(beginWord string, endWord string, wordList []string) [][]string {

	start := make(map[string]struct{})
	for _, v := range wordList {
		start[v] = struct{}{}
	}
	delete(start, beginWord)
	if _, ok := start[endWord]; !ok {
		return [][]string{}
	}
	route := []string{beginWord}
	resmap := make(map[string][]string)
	// 广度优先遍历获取映射结果
	for len(route) != 0 {
		tmp := make([]string, 0)
		for i := 0; i < len(route); i++ {

			origin := route[i]
			// if _, ok := start[origin]; !ok {
			// 	continue
			// }
			borigin := []byte(origin)
			// 每一位字符转换为其他26位英文字母
			for j := 0; j < len(origin); j++ {
				oc := borigin[j]
				for k := 0; k < 26; k++ {
					if byte(int('a')+k) == oc {
						continue
					}
					borigin[j] = byte(int('a') + k)
					if _, ok := start[string(borigin)]; ok {
						isFind := false
						if v, ok := resmap[string(borigin)]; ok {

							for _, tv := range v {
								if tv == origin {
									isFind = true
									break
								}
							}

						}
						if !isFind {
							resmap[string(borigin)] = append(resmap[string(borigin)], origin)
						}

						tmp = append(tmp, string(borigin))
						// delete(start, string(borigin))
					}
				}
				borigin[j] = oc
			}
			delete(start, origin)

		}
		for _, t := range tmp {
			delete(start, t)
		}
		route = tmp
	}
	res := make([][]string, 0)
	tmp := make([]string, 0)
	dfs(endWord, endWord, beginWord, &tmp, &resmap, &res)
	return res

}

func dfs(tmpstr string, endWord, beginWord string, tmp *[]string, route *map[string][]string, res *[][]string) {
	if tmpstr == beginWord {
		t := make([]string, len(*tmp)+1)
		for i := 0; i < len(*tmp); i++ {
			t[len(*tmp)-i-1] = (*tmp)[i]
		}
		t[len(t)-1] = endWord
		*res = append(*res, t)
		return

	}

	v, ok := (*route)[tmpstr]
	if ok {
		for _, ls := range v {
			*tmp = append(*tmp, ls)
			dfs(ls, endWord, beginWord, tmp, route, res)
			*tmp = (*tmp)[:len(*tmp)-1]
		}
	}
}

// @lc code=end

